/**
 * Counts the number of unique appearances of each entry in an {Array}.
 *
 * @returns {Array} where each item contains {"entry", "count"}. Sorted by
 *          count, descending.
 */
Array.prototype.uniqueCount = function() {
  var unique = {}, sorted = [];

  this.map(function (entry) {
    if (typeof unique[entry] == 'undefined') {
      unique[entry] = 1;
    } else {
      unique[entry] = 1 + unique[entry];
    }
  });

  for (type in unique) {
    sorted.push({"entry":type, "count":unique[type]});
  }

  sorted.sort(function(a, b) { return (b.count - a.count); });

  return sorted;
};

/**
 * Returns an array of unique elements in an {Array}.
 *
 * @returns {Array}
 */
Array.prototype.unique = function() {
  var unique = {}, result = [];

  this.map(function (entry) {
    unique[entry] = 1;
  });

  for (type in unique) {
    result.push(type);
  }

  return result;
};

/**
 * Aggregates the items in an array using the default aggregation operation
 * (e.g. array[0] + array[1]).
 *
 * @returns The resulting aggregation.
 */
Array.prototype.aggregate = function() {
  var result = this[0];

  for (var i = 1; i < this.length; i++) {
    result = result + this[i];
  }

  return result;
};

// overlap clustering
function overlap() {
  var overlap = {},
      points = [],
      padding = 0,
      radius = function(d) { return 8; },
      clusterRadius = function(c) { return 6 + 2 * Math.sqrt(c.size); };

  overlap.radius = function(x) {
    if (!arguments.length) return radius;
    radius = x;
    return overlap;
  };

  overlap.clusterRadius = function(x) {
    if (!arguments.length) return clusterRadius;
    clusterRadius = x;
    return overlap;
  };

  overlap.padding = function(x) {
    if (!arguments.length) return padding;
    padding = x;
    return overlap;
  };

  overlap.add = function(x, data) {
    x.data = data;
    points.push(x);
    return overlap;
  };

  overlap.cluster = function() {
    var clusters = points.map(function(p) {
      return {
        'x':p.x,
        'y':p.y,
        'radius':radius(p.data),
        'size':1,
        'points':[p]
      };
    });

    var quadtree = d3.geom.quadtree(clusters);

    /**
     * Returns an array of nodes that collide with the specified node.
     */
    var getCollisions = function(d) {
      var collisions = [];
      var r = d.radius + padding,
      nx1 = d.x - r,
      nx2 = d.x + r,
      ny1 = d.y - r,
      ny2 = d.y + r;

      quadtree.visit(function(quad, x1, y1, x2, y2) {
        if (quad.point && (quad.point !== d)) {
          var x = d.x - quad.point.x,
              y = d.y - quad.point.y,
              l = Math.sqrt(x * x + y * y),
              r = d.radius + quad.point.radius + padding;

          if (l < r) {
            collisions.push(quad.point);
          }
        }

        return x1 > nx2
            || x2 < nx1
            || y1 > ny2
            || y2 < ny1;
      });

      return collisions;
    };

    /**
     * Merges the selected collisions into clusters[i].
     *
     * @param clusters
     * @param i
     * @param collisions
     */
    function merge(clusters, i, collisions) {
      var cluster = clusters[i];

      collisions.map(function (collision) {
        collision.points.map(function (point) {
          cluster.points.push(point);
        });

        var totalSize = cluster.size + collision.size;
        var ratioA = cluster.size / totalSize;
        var ratioB = collision.size / totalSize;
        cluster.x = (cluster.x * ratioA) + (collision.x * ratioB);
        cluster.y = (cluster.y * ratioA) + (collision.y * ratioB);

        collision.merged = true;
      });

      cluster.size = cluster.points.length;
      cluster.radius = clusterRadius(cluster);
    }

    // Keep merging until there are no more collisions.
    for (var i = 0; i < clusters.length; i++) {
      quadtree = d3.geom.quadtree(clusters);
      var collisions = getCollisions(clusters[i]);

      // If there are any collisions, merge them into the current cluster and
      // re-evaluate.
      // TODO(alanv): This is not optimal and with a dense graph will result in
      // one giant cluster.
      if (collisions.length > 0) {
        merge(clusters, i, collisions);
        clusters = clusters.filter(function (d) { if (d.merged) return false; return true; });
        i--;
      }
    }

    return clusters;
  };

  return overlap;
}

// Returns a methods that finds collisions between d and all other circles.
function collide() {
  var quadtree = d3.geom.quadtree(nodes);

  return function(d) {
    var r = d.radius + radius.domain()[1] + padding,
        nx1 = d.x - r,
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;

    quadtree.visit(function(quad, x1, y1, x2, y2) {
      if (quad.point && (quad.point !== d)) {
        var x = d.x - quad.point.x,
            y = d.y - quad.point.y,
            l = Math.sqrt(x * x + y * y),
            r = d.radius + quad.point.radius + (d.color !== quad.point.color) * padding;

        if (l < r) {
          collisions.push(quad.point);
        }
      }

      return x1 > nx2
          || x2 < nx1
          || y1 > ny2
          || y2 < ny1;
    });
  };
}

var clusteringEnabled = true;

// Toggles clustering off and on.
function setIconClustering(enabled) {
  clusteringEnabled = enabled;

  d3.selectAll("g.icon_cluster")
    .each(function() {
      this.cluster.show(enabled);
    });
}

// Clustering implementation specific to NICS.
function clusterIcons(e) {
  // Extract only the icon features.
  var icons = e.features.filter(function(elem) {
    return (typeof elem.data.style.icon != 'undefined');
  });

  // Create the object used to cluster overlapping elements.
  var overlapping = e.tile.overlap || (e.tile.overlap = overlap()
      .radius(function (icon) { return (icon.element.getAttribute("width") / 2); })
      .clusterRadius(function (cluster) {
        // Only compute the estimated cluster radius if the size changes.
        if (cluster.__size != cluster.size) {
          var entries = cluster.points.map(function(p) { return p.data.data.style.icon.href; });
          var unique = entries.uniqueCount();
          var estimate = (unique.length > 1) ? (16 + 4 * Math.sqrt(unique[0].count)) : 10;
          cluster.__estimate = estimate;
        }
        return cluster.__estimate;
      })
      .padding(4));

  // Add icons to clustering object.
  icons.map(function(icon) { overlapping.add(icon.data.geometry.coordinates, icon); });

  var svg = d3.select(e.tile.element);
  var clusters = overlapping.cluster();

  // Count unique icons within a cluster, then
  // collapse clusters with too many items.
  clusters.map(function (cluster) {
    var types = cluster.points.map(function(point) { return point.data.data.style.icon.href; });
    var unique = types.uniqueCount();

    // Collapse clusters with too many items.
    if (unique.length > 3) {
      var remainder = unique.slice(2);
      unique = unique.slice(0, 2);
      unique.push({
        "entry": remainder.map(function(e) { return e.entry; }),
        "count": remainder.map(function(e) { return e.count; }).aggregate()
      });
    }

    cluster.unique = unique;
  });

  // Assign cluster points to classes.
  clusters.map(function (cluster, i) {
    cluster.points.map(function (point) {
      var element = point.data.element;
      var elementClass = element.getAttribute("class");
      element.setAttribute("class", elementClass + " icon_cluster_" + i);
      element.cluster = cluster;
    });
  });

  var showCluster = function(c) {
    var self = d3.select(c.element);
    var points = d3.selectAll(c.points.map(function (p) { return p.data.element; }));
    if (points[0].length > 1) {
      var transform = "translate(" + c.x + ", " + c.y + ")";
      points
        .transition()
        .attr("transform", transform)
        .style("opacity", 0.0)
        .transition().delay(1000)
        .style("opacity", 1.0)
        .style("display", "none")
        .attr("transform", function(p) {
          var c = p.data.geometry.coordinates;
          return "translate(" + c.x + "," + c.y + ")";
        });
      self
        .style("display", "block")
        .attr("transform", transform + " scale(0)")
        .transition()
        .attr("transform", transform)
        .style("opacity", 1.0);
    } else {
      points.style("display", "none");
      self.style("display", "block");
    }
  };

  var hideCluster = function(c) {
    var self = d3.select(c.element);
    var points = d3.selectAll(c.points.map(function (p) { return p.data.element; }));

    if (points[0].length > 1) {
      var transform = "translate(" + c.x + ", " + c.y + ")";
      self
        .style("opacity", 1.0)
        .transition()
        .attr("transform", transform + " scale(0)")
        .style("opacity", 0.0)
        .transition().delay(1000)
        .style("opacity", 1.0)
        .style("display", "none");
      points
        .style("opacity", 0.0)
        .style("display", "block")
        .transition()
        .attr("transform", function(p) {
          var c = p.data.geometry.coordinates;
          return "translate(" + c.x + "," + c.y + ")";
        })
        .style("opacity", 1.0)
        .style("display", "block");
    } else {
      self.style("display", "none");
      points.style("display", "block");
    }
  };

  // Create groups for clustered icons.
  var icon_clusters = svg.selectAll("g.icon_cluster")
      .data(clusters)
    .enter().append("g")
      .attr("class", function(c, i) { return "icon_cluster icon_cluster_" + i; })
      .attr("transform", function(c) { return "translate(" + c.x + ", " + c.y + ")"; })
      .each(function (c) {
        c.element = this;
        c.element.cluster = c;
        c.show = function(enable) {
          if (enable) {
            showCluster(c);
          } else {
            hideCluster(c);
          }
        };
      });

  // Hide all original icons so that we can animate them later.
  icon_clusters
      .each(function (c, i) {
        d3.selectAll(c.points.map(function (p) { return p.data.element; }))
          .style("display", "none");
      });

  // Create simple icons for clusters with only one item.
  icon_clusters.filter(function(c) { return (c.size == 1); })
      .append("image")
      .attr("height", function(c) { return 20; })
      .attr("width", function(c) { return this.getAttribute("height"); })
      .attr("transform", function(c) { return "translate(-10,-10)"; })
      .attr("xlink:href", function(c) { return c.unique[0].entry; });

  // Create compound icons for clusters with multiple items.
  var multi_clusters = icon_clusters.filter(function(c) { return (c.size > 1); });

  // Assign properties to unique clusters.
  clusters.map(function(c) {
    var angle = (Math.PI * 2) / c.unique.length;
    var padding = (c.unique.length > 2) ? 2 : 0;
    var useOffset = (c.unique.length > 1);
    c.unique.map(function(u, i) {
      u.radius = (8 + 2 * Math.sqrt(u.count));
      u.angle = (angle * i);
      u.x = useOffset ? (u.radius + padding) * Math.cos(u.angle) : 0;
      u.y = useOffset ? (u.radius + padding) * Math.sin(u.angle) : 0;
    });
  });

  // Create lookup table for angles.
  var angles = [];
  for (var angle = 0; angle < Math.PI*2; angle += Math.PI/8) {
    angles.push({"cos": Math.cos(angle), "sin": Math.sin(angle)});
  }

  // Generate convex hulls for vertices.
  multi_clusters.selectAll("path.icon_cluster_hull")
      .data(function(c) {
        var vertices = [];
        // Add vertices for clustered markers.
        c.points.map(function(p) {
          var padding = (10 + 2);
          var rel_x = (p.x - c.x);
          var rel_y = (p.y - c.y);
          for (var i = 0; i < angles.length; i++) {
            vertices.push(
                [rel_x + (padding * angles[i].cos),
                 rel_y + (padding * angles[i].sin)]);
          }
        });
        // Add vertices for cluster icons.
        c.unique.map(function(u) {
          var padding = (u.radius + 2);
          for (var i = 0; i < angles.length; i++) {
            vertices.push(
                [u.x + (padding * angles[i].cos),
                 u.y + (padding * angles[i].sin)]);
          }
        });
        return [d3.geom.hull(vertices)];
      })
    .enter().append("path")
      .attr("class", "icon_cluster_hull")
      .attr("d", function(d) { return "M" + d.join("L") + "Z"; });

  // Generate icon cluster groups.
  var compound_icons = multi_clusters.selectAll("g.compound_icon")
      .data(function(c) { return c.unique; })
    .enter().append("g")
      .attr("class", "compound_icon");

  // Everything has a background circle.
  compound_icons
      .append("circle")
      .attr("class", "icon_cluster")
      .attr("r", function(u) { return u.radius; })
      .attr("cx", function(u) { return u.x; })
      .attr("cy", function(u) { return u.y; });

  // Only single-item icons have images.
  compound_icons.filter(function(u) { return typeof(u.entry) == "string"; })
      .append("image")
      .attr("class", "icon_cluster")
      .attr("width", function(u) { return (u.radius * 2); })
      .attr("height", function(u) { return (u.radius * 2); })
      .attr("x", function(u) { return u.x - u.radius; })
      .attr("y", function(u) { return u.y - u.radius; })
      .attr("xlink:href", function(u) { return u.entry; });

  // Only multiple-item icons have text.
  compound_icons.filter(function(u) { return typeof(u.entry) == "object"; })
      .append("text")
      .attr("class", "cluster_label")
      .attr("x", function(u) { return u.x; })
      .attr("y", function(u) { return u.y + u.radius * 0.15; })
      .style("font-size", function(u) { return u.radius; })
      .text(function(u) { return "+" + u.count; });

  // Apply user preference.
  if (!clusteringEnabled) {
    setIconClustering(false);
  }
}
